package xjggb.algorithm.优先队列.heap;

import xjggb.algorithm.二叉堆.printer.BinaryTreeInfo;

import java.util.Comparator;

public class BinaryHeap<E> extends AbstractHeap<E> implements BinaryTreeInfo {

    /*
    * 定义数组
    * */
    private E[] elements;

    /*
    * 默认长度
    * */
    private static final int DEFAULT_CAPACITY = 10;


    public BinaryHeap(E[] elements, Comparator<E> comparator)  {
        super(comparator);

        if (elements == null || elements.length == 0) {
            this.elements = (E[]) new Object[DEFAULT_CAPACITY];
        } else {
            size = elements.length;
            int capacity = Math.max(elements.length, DEFAULT_CAPACITY);
            this.elements = (E[]) new Object[capacity];
            for (int i = 0; i < elements.length; i++) {
                this.elements[i] = elements[i];
            }
            heapify();
        }
    }


    public BinaryHeap() {
        this(null, null);
    }


    /*
    * 清除数据
    * */
    @Override
    public void clear() {
        for (int i = 0; i <size ; i++) {
            elements[i]=null;
        }
        size=0;
    }


    @Override
    public void add(E element) {
        elementNotNullCheck(element);  //判断是否为null
        ensureCapacity(size + 1);    //判断容量是否充足
        elements[size++]=element;    //添加元素
        siftUp(size-1);
    }

    /*
    * 元素上滤
    * */
    private void siftUp(int index) {
        E e = elements[index];
        while (index>0){
            int pindex  = (index - 1) >> 1;  //寻找父节点如果 i > 0 ，它的父节点的索引为( (i – 1) / 2 )
            E p = elements[pindex];  //得到父节点
            if (compare(e,p)<=0) return;  //新添加节点小于父节点直接返回
            //交换 index、pindex位置的内容
            E tmp = elements[index];
            elements[index]=elements[pindex];  //进行交换
            elements[pindex]=tmp;
            index=pindex;
        }
    }


    /*
    * 对数组进行扩容
    * */
    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length; //获取数组的长度
        if (oldCapacity>=capacity)return;
        //新容量为就容量的1.5倍
        int newCapacity  = oldCapacity + (oldCapacity >> 1);
        E[] newElements = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[i];  //将元素赋值给另一个新的数组
        }
        elements = newElements;   //给数组赋值
    }
    /*
    * 获取节点元素
    * */
    @Override
    public E get() {
        emptyCheck();  // 判断数组是否为零
        return elements[0];  //获取头结点
    }

    /*
    * 判断元素是否为零
    * */
    private void emptyCheck() {
        if (size==0){
            throw new IndexOutOfBoundsException("get size  null");
        }

    }

    @Override
    public E remove() {
        emptyCheck();
        int lastIndex  = --size;
        E element = elements[0];  //获取第0个元素
         elements[0] = elements[lastIndex]; //把最后一个元素赋值给0元素
        elements[lastIndex]=null;  //清空最后的元素
        siftDown(0);  //下移
        return element;
    }

    /*
    * 元素下率
    * */
    private void siftDown(int index) {
        E element = elements[index];
        int half = size >> 1;
        // 第一个叶子节点的索引 == 非叶子节点的数量
        // index < 第一个叶子节点的索引
        // 必须保证index位置是非叶子节点

        while (index<half){
            // index的节点有2种情况
            // 1.只有左子节点
            // 2.同时有左右子节点

            // 默认为左子节点跟它进行比较
            int childIndex = (index << 1) + 1;
            E child = elements[childIndex];

            // 右子节点
            int rightIndex = childIndex + 1;

            // 选出左右子节点最大的那个
            if (rightIndex < size && compare(elements[rightIndex], child) > 0) {
                child = elements[childIndex = rightIndex];
            }

            if (compare(element, child) >= 0) break;

            // 将子节点存放到index位置
            elements[index] = child;
            // 重新设置index
            index = childIndex;
        }
        elements[index] = element;
    }

    @Override
    public E replace(E element) {
        elementNotNullCheck(element);

        E root = null;
        if (size == 0) {
            elements[0] = element;
            size++;
        } else {
            root = elements[0];
            elements[0] = element;
            siftDown(0);
        }
        return root;
    }


    /**
     * 批量建堆
     */
    private void heapify() {
        // 自上而下的上滤
//		for (int i = 1; i < size; i++) {
//			siftUp(i);
//		}

        // 自下而上的下滤
        for (int i = (size >> 1) - 1; i >= 0; i--) {
            siftDown(i);
        }
    }


    /*
    * 判断添加元素是否为null
    * */
    private void elementNotNullCheck(E element) {
        if (element==null){
            throw new IllegalArgumentException(" add to element  null");
        }
    }


    @Override
    public Object root() {
        return 0;
    }

    @Override
    public Object left(Object node) {
        int index = ((int)node << 1) + 1;
        return index >= size ? null : index;
    }

    @Override
    public Object right(Object node) {
        int index = ((int)node << 1) + 2;
        return index >= size ? null : index;
    }

    @Override
    public Object string(Object node) {
        return elements[(int)node];
    }
}
